1. Field of the Invention
The present invention relates to an apparatus and method for performing digital signal processing, and in particular, for performing the fast Fourier transform (FFT).
2. Description of the Related Art
The fast Fourier transform is a common digital processing technique for use in performing, for example, spectral analysis and filtering of digital data. Several applications, such as radar, sonar, communications surveillance, and image processing, require high speed digital signal processing in order to achieve the real-time performance required by these applications. Presently, however, the known hardware for performing a FFT on the data produced in these applications is physically quite large and very expensive. As a consequence, presently known hardware for performing FFT processing has proven to be impractical in many of these applications. Moreover, due to the relatively large size of the hardware, typically covering several printed circuit boards and possibly including several racks of equipment, propagation delays associated with transferring information between the various elements comprising the FFT processing hardware and the like have steadily eroded the ability of the hardware to accommodate the eve increasing data rates employed in the aforementioned types of applications. Consequently, there is a need for a device for accomplishing FFT processing that addresses the drawbacks associated with the size of presently known FFT processing hardware. Additionally, there is a need for a device for accomplishing FFT processing that is less expensive than presently known FFT devices.
In many digital signal processing applications, the digital data must be subjected either before or after the FFT to a related FFT operation, such as windowing, in order to achieve the desired result. Presently known FFT processing hardware does not incorporate the ability to perform these related FFT functions. Consequently, to implement related FFT functions, additional hardware must be interfaced with the FFT processing hardware. Due to the size of presently known FFT processing hardware and the time constraints that the size of the FFT processing hardware imposes, the need to incorporate additional hardware to realize related FFT functions further reduces the speed at which such systems can operate as well as adds to the complexity of the system. Consequently, such systems are unsuitable for many of the aforementioned high-speed real-time applications. Based on the foregoing, there is also a need for a device that integrates the ability to accomplish an FFT with related FFT functions that are typically employed in digital signal processing.
In digital signal processing applications, such as graphics, it is typically necessary to subject the digital data to a vector add/subtract and bit-wise logical operation, for example. Presently known digital signal processing hardware implements these types of operations or functions discretely. This lack of integrated functionality requires that several separate pieces of hardware be incorporated into the digital signal processing system to realize the required functionality for many applications. As with the related FFT functions, this typically renders the resulting system unsuitable for many high-speed applications as well as increases the complexity of such systems.
In many applications, the digital data on which an FFT is to be performed lacks any imaginary component, i.e., the digital data includes only a real component. In these instances, a FFT can be more efficiently or quickly performed on the digital data using the FFT2N algorithm, which recombines a FFT of N complex-points into a FFT of 2N real points, to realize an increase in throughput. The FFTNN algorithm, which recombines an FFT of N complex-points into two separate N real-point FFTs, provides similar benefits in the appropriate situation. Many applications for FFT processing are quickly approaching the point where the increase in throughput realized by implementing the FFT2N and/or FFTNN method will be needed to realize real-time constraints and/or provide additional time for further processing of the digital data.
Most, if not all, of the known processors for implementing the FFT achieve a defined arithmetic precision using a fixed point integer/fixed scaling method. The use of a fixed point integer/fixed scaling method, however, limits the dynamic range and numerical accuracy of the information produced by the processor. Consequently, there is a need for a processor for performing FFT functions where the numerical accuracy and dynamic range of the information produced by the processor is increased relative to known FFT processors.
Presently known digital signal processors employ one unidirectional bus to transfer data from an input memory to the processor and another unidirectional bus is used to transfer data from the processor to an output memory or employ a single bidirectional bus to alternatingly read and write to a single input/output memory. Many applications require recursive processing of data where the data output by the processor during one iteration of the recursive processing becomes the input data for a subsequent iteration. In FFT processors that employ separate unidirectional buses, recursive processing typically requires hardware for moving data from the output memory to the input memory for each iteration. The need for this additional hardware typically results in a reduction in throughput as well as increasing the complexity and cost of the processing hardware necessary to implement recursive processing. FFT processors that employ a single bidirectional bus are inherently performance limited by their inability to simultaneously perform input data transfers and output data transfers. Consequently, there is also a need for a digital signal processor that increases the throughput or speed at which recursive processing can be accomplished.
Most, if not all, digital signal processors support only one mechanism to transfer data into and out of the digital signal processor. To increase performance in such a situation, the speeds of all data transfer buses and input/output memories must be increased proportionately, with performance normally being limited by available memory speeds. In many situations, however, employing high speed input/output memories leads to an unacceptable increase in the cost of a digital signal processing system. Consequently, there is also a need for a digital signal processor that supports multiple mechanisms to transfer data into and out of the digital signal processor and, in so doing, allows a digital signal processing system to be constructed that accommodates available memory speeds and/or cost constraints.